package systematic.algorithm.bit;

/**
 * 打印出现奇数次的数
 * 
 * @author lisy
 */
public class EvenTimesOddTimes {

	/**
	 * 数组中，只有一种数，出现奇数次
	 */
	public static void printOddTimesNum1(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
		}
		System.out.println(eor);
	}

	/**
	 * 数组中，有两种数，出现奇数次
	 */
	public static void printOddTimesNum2(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
		}
		// 提取出最右的 1(两个数在此位置值不同)，相当于 eor & (~eor + 1)
		int rightOne = eor & (-eor); 
		
		int onlyOne = 0;
		for (int i = 0 ; i < arr.length;i++) {
			// 只处理指定位数为 1 的数
			if ((arr[i] & rightOne) != 0) {
				onlyOne ^= arr[i];
			}
		}
		System.out.println(onlyOne + " " + (eor ^ onlyOne));
	}

	public static void main(String[] args) {
		int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
		printOddTimesNum1(arr1);

		int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
		printOddTimesNum2(arr2);
	}

}
